package com.java.comprehensive.arithmetic.leecode.easy;

import util.TreeNode;

/**
 * @program: comprehensive-service
 * @description: 平衡二叉树
 * @author: 窦绍飞
 * @create: 2021-12-02 10:39
 **/
public class LeetCode_110 {

	public static boolean isBalanced(TreeNode root) {
		if (root == null) {
			return true;
		} else {
			return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
		}
	}

	public static int height(TreeNode root) {
		if (root == null) {
			return 0;
		} else {
			return Math.max(height(root.left), height(root.right)) + 1;
		}
	}

	public boolean isBalanced2(TreeNode root) {
		return height2(root) >= 0;
	}

	public int height2(TreeNode root) {
		if (root == null) {
			return 0;
		}
		int leftHeight = height(root.left);
		int rightHeight = height(root.right);
		if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) {
			return -1;
		} else {
			return Math.max(leftHeight, rightHeight) + 1;
		}
	}


	public static void main(String[] args) {
		TreeNode treeNode5 = new TreeNode(3, null, null);
		TreeNode treeNode6 = null;
		TreeNode treeNode7 = null;
		TreeNode treeNode8 = new TreeNode(4, null, null);
		TreeNode treeNode9 = new TreeNode(4, null, null);
		TreeNode treeNode3 = new TreeNode(2, treeNode6, treeNode7);
		TreeNode treeNode4 = new TreeNode(3, treeNode8, treeNode9);
		TreeNode treeNode2 = new TreeNode(2, treeNode4, treeNode5);
		TreeNode treeNode = new TreeNode(1, treeNode2, treeNode3);
		isBalanced(treeNode);
	}
}
